package com.shm.leetcode;

import java.util.TreeSet;

/**
 * 363. 矩形区域不超过 K 的最大数值和
 * 给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。
 *
 * 题目数据保证总会存在一个数值和不超过 k 的矩形区域。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：matrix = [[1,0,1],[0,-2,3]], k = 2
 * 输出：2
 * 解释：蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。
 * 示例 2：
 *
 * 输入：matrix = [[2,2,-1]], k = 3
 * 输出：3
 *
 *
 * 提示：
 *
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= m, n <= 100
 * -100 <= matrix[i][j] <= 100
 * -105 <= k <= 105
 *
 *
 * 进阶：如果行数远大于列数，该如何设计解决方案？
 * @author SHM
 */
public class MaxSumSubmatrix {
    /**
     * 一、暴力 + 动态规划
     * 枚举矩形的 左上角、右下角，从 (i1, j1) 到 (i2, j2)
     * 从左上角、到右下角的矩形区域数值和：黄色 = 绿色 + 橙色 - 蓝色 + (i2, j2)
     * 状态转移方程为 dp(i1,j1,i2,j2) = dp(i1,j1,i2 - 1,j2) + dp(i1,j1,i2,j2 - 1) - dp(i1,j1,i2 - 1,j2 - 1) + matrix[i2 - 1][j2 - 1];
     * 四层遍历，时间复杂度 O(m^2n^2)O(m
     * 2
     *  n
     * 2
     *  )，空间复杂度 O(m^2n^2)O(m
     * 2
     *  n
     * 2
     *  )
     * 超出内存限制
     * 思路有戏，进一步压缩状态试试
     *
     * 作者：lzhlyle
     * 链接：https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/solution/javacong-bao-li-kai-shi-you-hua-pei-tu-pei-zhu-shi/
     * @param matrix
     * @param k
     * @return
     */
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int m = matrix.length,n=matrix[0].length;
        int[][][][] dp=new int[m+1][n+1][m+1][n+1];
        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= m; i++) {
                for (int l = 1; l <= n; l++) {
                    dp[i][l][i][l]=matrix[i-1][l-1];
                    for (int j = i; j <= m; j++) {
                        for (int r = l; r <= n; r++) {
                            dp[i][l][j][r] = dp[i][l][j-1][r]+dp[i][l][j][r-1]-dp[i][l][j-1][r-1]+matrix[j-1][r-1];
                            if (dp[i][l][j][r]<=k&&dp[i][l][j][r]>max){
                                max = dp[i][l][j][r];
                            }
                        }
                    }
                }

        }
        return max;
    }

    /**
     * 二、暴力 + 动态规划 + 状态压缩
     * 从上述代码发现，每次更换左上角 (i, j) 之后，之前记录的值都没用过了
     * 尝试每次更换左上角时就重复利用 dp，故只需记录右下角即可
     * 依然四层遍历，时间复杂度 O(m^2n^2)O(m
     * 2
     *  n
     * 2
     *  )，空间复杂度 O(mn)O(mn)
     *
     * 作者：lzhlyle
     * 链接：https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/solution/javacong-bao-li-kai-shi-you-hua-pei-tu-pei-zhu-shi/
     * @param matrix
     * @param k
     * @return
     */
    public int maxSumSubmatrix_2(int[][] matrix, int k) {
        int m = matrix.length,n=matrix[0].length;
        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= m; i++) {
            for (int l = 1; l <= n; l++) {
                int[][] dp=new int[m+1][n+1];
                dp[i][l]=matrix[i-1][l-1];
                for (int j = i; j <= m; j++) {
                    for (int r = l; r <= n; r++) {
                        dp[j][r] = dp[j-1][r]+dp[j][r-1]-dp[j-1][r-1]+matrix[j-1][r-1];
                        if (dp[j][r]<=k&&dp[j][r]>max){
                            max = dp[j][r];
                        }
                    }
                }
            }

        }
        return max;
    }

    public int maxSumSubmatrix_3(int[][] matrix, int k) {
        int rows = matrix.length, cols = matrix[0].length, max = Integer.MIN_VALUE;
        // O(cols ^ 2 * rows)
        for (int l = 0; l < cols; l++) { // 枚举左边界
            int[] rowSum = new int[rows]; // 左边界改变才算区域的重新开始
            for (int r = l; r < cols; r++) { // 枚举右边界
                for (int i = 0; i < rows; i++) { // 按每一行累计到 dp
                    rowSum[i] += matrix[i][r];
                }
                max = Math.max(max, dpmax(rowSum, k));
                if (max == k) return k; // 尽量提前
            }
        }
        return max;
    }
    // 在数组 arr 中，求不超过 k 的最大值
    private int dpmax(int[] arr, int k) {
        int rollSum = arr[0], rollMax = rollSum;
        // O(rows)
        for (int i = 1; i < arr.length; i++) {
            if (rollSum > 0) rollSum += arr[i];
            else rollSum = arr[i];
            if (rollSum > rollMax) rollMax = rollSum;
        }
        if (rollMax <= k) return rollMax;
        // O(rows ^ 2)
        int max = Integer.MIN_VALUE;
        for (int l = 0; l < arr.length; l++) {
            int sum = 0;
            for (int r = l; r < arr.length; r++) {
                sum += arr[r];
                if (sum > max && sum <= k) max = sum;
                if (max == k) return k; // 尽量提前
            }
        }
        return max;
    }

//    作者：lzhlyle
//    链接：https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/solution/javacong-bao-li-kai-shi-you-hua-pei-tu-pei-zhu-shi/


    /**
     * 方法一：有序集合
     * 思路
     *
     * 我们枚举矩形的上下边界，并计算出该边界内每列的元素和，则原问题转换成了如下一维问题：
     *
     * 给定一个整数数组和一个整数 kk，计算该数组的最大区间和，要求区间和不超过 kk。
     *
     * 定义长度为 nn 的数组 aa 的前缀和
     *
     * S_i = \begin{cases} 0&i=0\\ a_0+a_1+\cdots+a_{i-1}&1\le i\le n \end{cases}
     * S
     * i
     * ​
     *  ={
     * 0
     * a
     * 0
     * ​
     *  +a
     * 1
     * ​
     *  +⋯+a
     * i−1
     * ​
     *
     * ​
     *
     * i=0
     * 1≤i≤n
     * ​
     *
     *
     * 则区间 [l,r)[l,r) 的区间和 a_l+a_{l+1}+\cdots+a_{r-1}a
     * l
     * ​
     *  +a
     * l+1
     * ​
     *  +⋯+a
     * r−1
     * ​
     *   可以表示为 S_r-S_lS
     * r
     * ​
     *  −S
     * l
     * ​
     *  。
     *
     * 枚举 rr，上述问题的约束 S_r-S_l\le kS
     * r
     * ​
     *  −S
     * l
     * ​
     *  ≤k 可以转换为 S_l\ge S_r-kS
     * l
     * ​
     *  ≥S
     * r
     * ​
     *  −k。要使 S_r-S_lS
     * r
     * ​
     *  −S
     * l
     * ​
     *   尽可能大，则需要寻找最小的满足 S_l\ge S_r-kS
     * l
     * ​
     *  ≥S
     * r
     * ​
     *  −k 的 S_lS
     * l
     * ​
     *  。我们可以在枚举 rr 的同时维护一个存储 S_i\ (i<r)S
     * i
     * ​
     *   (i<r) 的有序集合，则可以在 O(\log n)O(logn) 的时间内二分找到符合要求的 S_lS
     * l
     * ​
     *  。
     *  复杂度分析
     *
     * 时间复杂度：O(m^2n\log n)O(m
     * 2
     *  nlogn)。其中 mm 和 nn 分别是矩阵 \textit{matrix}matrix 的行数和列数。
     *
     * 空间复杂度：O(n)O(n)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/solution/ju-xing-qu-yu-bu-chao-guo-k-de-zui-da-sh-70q2/
     * @param matrix
     * @param k
     * @return
     */
    public int maxSumSubmatrix_4(int[][] matrix, int k) {
        int m = matrix.length, n = matrix[0].length;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < m; i++) {
            int[] sum = new int[n];
            for (int j = i; j < m; j++) {
                for (int l = 0; l < n; l++) {
                    sum[l]+=matrix[j][l];
                }
                TreeSet<Integer> set = new TreeSet<>();
                set.add(0);
                int s=0;
                for (int v : sum) {
                    s+=v;
                    Integer ceiling = set.ceiling(s-k);
                    if (ceiling!=null){
                        max = Math.max(max,s-ceiling);
                    }
                    set.add(s);
                }
            }
        }
        return max;
    }
}
